package ch20;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;

import org.omg.CORBA.IRObject;

/**
 * Write a program to find the longest word made of other words.
 * 
 * @author Ray
 *
 */
public class ch20_7 {
	
	public static class LengthComparator implements Comparator<String>{
		public int compare(String o1, String o2){
			if(o1.length()<o2.length()) return 1;
			if(o1.length()>o2.length()) return -1;
			return 0;
		}
	}
	/**
	 * This is the simple case that "batti" and "batting" cannot in the array
	 * at the same time.
	 * @param words
	 * @return
	 */
	public static String longestWord(String[] words){
		Arrays.sort(words, new LengthComparator());
		for(int i=0;i<words.length;i++){
			String temp = words[i];
			String backup = new String(temp);
			for(String other: words){
				if(!other.equals(backup) && temp.contains(other))
					temp = temp.replace(other, "");
			}
			if(temp.length()==0) return backup;
		}
		return null;
	}
	
	/**
	 * This can handle all cases, including backtrack.
	 */
	static HashSet<String> set = new HashSet<>();
	
	public static String longestWord_allcases(String[] words){
		Arrays.sort(words, new LengthComparator());
		for(int i=0;i<words.length;++i){
			set.add(words[i]);
		}
		for(int i=0;i<words.length;++i){
			if(makeOfWords(words[i],words[i].length()))
				return words[i];
		}
		return null;
		
	}
	
	public static boolean makeOfWords(String word, int length){
		int len = word.length();
		if(len==0) return true;
		for(int i=1;i<=len;++i){
			if(i==length) return false;
			String temp = word.substring(0,i);
			if(set.contains(temp) && makeOfWords(word.substring(i), length))
				return true;
		}
		return false;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		String[] test = {"test", "tester", "testertest", "testing", 
                "apple", "seattle", "banana",  "batting", "ngcat", 
                "batti","bat", "testingtester", "testbattingcat"};
		System.out.println(longestWord(test));
		System.out.println(longestWord_allcases(test));
	}

}
